Hoàng Hối Khanh đỗ Thái học sinh đời Trần Thuận Tông. Bấy giờ nhà Trần đã suy yếu, quyền hành trong tay Hồ Quý Ly.

Tháng 8 năm 1391, uy quyền của Hồ Quý Ly ngày một to lớn, các tướng ở Hóa Châu là Phan Mãnh và Chu Bỉnh Khuê cùng nhau bàn luận về việc Hồ Quý Ly sắp lấy ngôi nhà Trần. Hoàng Hối Khanh và Đặng Tất viết thư báo cho Quý Ly biết, Quý Ly bèn giết hai người ấy và bổ dụng Hoàng Hối Khanh làm Chính hình viện đại phu và Đặng Tất làm Châu phán.

Năm 1400, Hồ Quý Ly cướp ngôi nhà Trần, lập ra nhà Hồ, đổi tên nước là Đại Ngu. Hoàng Hối Khanh được trọng dụng.

Năm 1404, để tăng cường kiểm soát nhân khẩu cho việc gọi lính, ông dâng lên kế sách lên Hồ Quý Ly lập hộ tịch rồi yêu cầu nhân dân kê khai, ghi tên các nam thiếu niên từ 12 tuổi trở lên, chép vào sổ bộ để thống kê số trong toàn quốc.

Hoàng Quảng Thành, thổ quan châu Tư Minh, tâu với vua Minh Thành Tổ (Chu Lệ) rằng Lộc Châu nguyên là đất cũ của châu Tư Minh. Minh Thành Tổ sai người sang Đại Ngu đòi trả lại đất Lộc Châu[1] cho châu Tư Minh, nhưng Quý Ly không nghe. Năm 1405, Chu Lệ lại sai sứ thần sang đòi, Quý Ly không thể từ chối, bèn cho Hối Khanh làm sung cát địa sứ để giao đất. Hối Khanh đem đất 59 thôn ở Cổ Lâu trả cho nhà Minh. Khi ông trở về, Hồ Quý Ly quở trách ông trả đất quá nhiều. Sau đó, những thổ quan do nhà Minh đặt ra để giữ đất mới nhượng ấy, Quý Ly ngầm sai người bản thổ đánh thuốc độc cho chết.

Tháng 9 năm 1405, Hồ Quý Ly sai ông đốc suất dân phu đắp thành Đa Bang (huyện Ba Vì, tỉnh Hà Tây ngày nay) để phòng chống quân Minh xâm lược.

Nhân lúc nhà Hồ chưa ổn định, Chiêm Thành quấy rối phía nam. Hồ Quý Ly sai Hoàng Hối Khanh làm Tuyên uý sứ trấn thủ cả vùng Thăng Hoa. Đến Thăng Hoa, Hối Khanh chọn Đặng Tất, Phạm Thế Căng và Nguyễn Lỗ giúp việc cho mình.